package zifuchuan

import "fmt"

func KMP(s string) []int {
	n := len(s)
	ans := make([]int, n)
	length := 0
	ans[0] = 0
	i := 1

	for i < n {
		if s[i] == s[length] {
			length++
			ans[i] = length
			i++
		} else {
			if length != 0 {
				length = ans[length-1]
			} else {
				ans[i] = 0
				i++
			}
		}
	}
	fmt.Println(ans)
	return ans
}

func computeLPSArray(pat string, M int) []int {
	lps := make([]int, M)
	length := 0 // length of the previous longest prefix suffix
	lps[0] = 0  // lps[0] is always 0
	i := 1

	for i < M {
		if pat[i] == pat[length] {
			length++
			lps[i] = length
			i++
		} else {
			if length != 0 {
				length = lps[length-1]
			} else {
				lps[i] = 0
				i++
			}
		}
	}
	return lps
}

func KMPSearch(pat string, txt string) {
	M := len(pat)
	N := len(txt)

	lps := computeLPSArray(pat, M)

	i := 0 // index for txt[]
	j := 0 // index for pat[]
	for i < N {
		if pat[j] == txt[i] {
			i++
			j++
		}

		if j == M {
			fmt.Printf("Found pattern at index %d ", i-j)
			j = lps[j-1]
		} else if i < N && pat[j] != txt[i] {
			if j != 0 {
				j = lps[j-1]
			} else {
				i++
			}
		}
	}
}

func KMP2(s string) []int {
	n := len(s)
	ans := make([]int, n)
	length := 0
	ans[length] = 0
	i := 1
	for i < n {
		if s[i] == s[length] {
			length++
			ans[i] = length
			i++
		} else {
			if length != 0 {
				length = ans[length-1]
			} else {
				ans[i] = 0
				i++
			}
		}
	}
	fmt.Println(ans)
	return ans
}

func KMP3(pattern, txt string) int {
	// 思路：首先进行比较，比较到达指出索引，错误修改位置
	next := KMP2(pattern)
	m, n := len(pattern), len(txt)
	if m == 0 {
		return -1
	}
	i, j := 0, 0
	for i < m {
		if pattern[i] == txt[j] {
			i++
			j++
		}
		if j == n {
			fmt.Println(i)
			return i
		} else if i < m && pattern[i] != txt[j] {
			if j > 0 {
				j = next[j-1]
			} else {
				i++
			}
		}
	}
	return -1
}
